#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ret = INT_MAX, n = baseCosts.size(), m = toppingCosts.size();
        for (int i = 0; i < n; i++) {
            vector<int> cur;
            unordered_map<int, int> hash;
            cur.push_back(baseCosts[i]);
            hash[baseCosts[i]];
            if (abs(ret - target) > abs(baseCosts[i] - target)) ret = baseCosts[i];
            else if ((abs(ret - target) == abs(baseCosts[i] - target)) && ret > baseCosts[i]) ret = baseCosts[i];
            for (int j = 0; j < m; j++) {
                int count = cur.size();
                for (int k = 0; k < count; k++) {
                    int tmp1 = cur[k] + toppingCosts[j], tmp2 = cur[k] + 2 * toppingCosts[j];
                    if (hash.count(tmp1) == 0) cur.push_back(tmp1), hash[tmp1];
                    if (hash.count(tmp2) == 0) cur.push_back(tmp2), hash[tmp2];
                    if (abs(ret - target) > abs(tmp1 - target)) ret = tmp1;
                    else if ((abs(ret - target) == abs(tmp1 - target)) && ret > tmp1) ret = tmp1;
                    if (abs(ret - target) > abs(tmp2 - target)) ret = tmp2;
                    else if ((abs(ret - target) == abs(tmp2 - target)) && ret > tmp2) ret = tmp2;
                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ret = INT_MAX, res = 2 * target - 1;
        for (auto num : baseCosts) ret = min(num, ret);
        if (ret > target) return ret;

        vector<bool> dp(target + 1, false);
        for (auto num : baseCosts) {
            if (num <= target) dp[num] = true;
            else res = min(res, num);
        }

        for (auto num : toppingCosts) {
            for (int i = 0; i < 2; i++) {
                for (int j = target; j > 0; j--) {
                    if (dp[j] && j + num > target) res = min(res, j + num);
                    else if (dp[j]) dp[j + num] = true;
                }
            }
        }

        for (int i = target; i > 0; i--)
            if (dp[i]) {
                if (abs(i - target) > abs(res - target)) ret = res;
                else ret = i;
                break;
            }

        return ret;
    }
};